Tracing is a specialized use of logging to record information about a program's execution. This information is typically used by programmers for debugging purposes, and additionally, depending on the type and detail of information contained in a trace log, by experienced system administrators or technical support personnel to diagnose common problems with software. Often times, tracing utilities implemented ring buffers as the data structure to store the information obtained by the trace utility. Tasks that write into the ring buffer are known as writers or producers. Tasks that read from the ring buffer are known as readers or consumers.
One problem with respect to a trace utility using a ring buffer for collecting data, is the race condition encountered by readers and writers of a ring buffer that is operating in overwrite mode. Overwrite mode refers to the mode of the ring buffer where if the writer was to fill up the buffer before the reader could free up anything, the writer would continue writing and overwrite the oldest data in the ring buffer. This mode loses the oldest events stored in the ring buffer. As a result, if a ring buffer is in overwrite mode, both the reader and the writer are capable of accessing the head page and pushing the head page forward in the ring buffer, creating the above-mentioned race condition.
The typical solution to handle the race condition between readers and writers in a ring buffer operating in overwrite mode is with counters. The reader would simply copy the data, and check if the writer had overwritten it since the reader read and copied the data. If it did, the reader would try to copy again. That is, the writer would set a bit in the counter to show that it is going to do a write. Then, the writer would write the data and clear the counter, as well as increment it. The reader would read the counter (waiting if the writer bit is set), read the data, and check the counter to make sure a write did not happen in the meantime. If a write did, the reader would need to read again.
The problem with the above counter approach is that multiple copies are needed. If the data in the ring buffer is to be passed off to higher layers, once this pass is made to the higher layer, the higher layer cannot be expected to check if a writer came by before the data was used. Furthermore, it is not desirable to have to copy the data before passing it off to the higher layer because of the expensive and inefficiency associated with that requirement.
As a result, a way to prevent the race condition between readers and writers of a ring buffer in overwrite mode without having to use counters and copying of the prior art solutions would be beneficial.